#!/usr/bin/env python
import heapq
import math
import sys

DEBUG = False

sys.setrecursionlimit(10000)

inicial = [7, 2, 4, 5, 0, 6, 8, 3, 1]
objetivo = [0, 1, 2, 3, 4, 5, 6, 7, 8]

def h(l):
    size = int(math.sqrt(len(l)))
    result = 0
    for i, a in enumerate(l):
        lin1, col1 = i / size, i % size
        target = objetivo.index(a)
        lin2, col2 = target / size, target % size
        result += abs(lin1 - lin2) + abs(col1 - col2)
    return result

class Jogo:
    def __init__(self):
        self.tabuleiro = inicial
    
    def copy(self):
        novo_jogo = Jogo()
        novo_jogo.tabuleiro = list(self.tabuleiro)
        return novo_jogo

    def _move(self, rel_lin, rel_col):
        index = self.tabuleiro.index(0)
        size = int(math.sqrt(len(self.tabuleiro)))
        lin1, col1 = index / size, index % size
        lin2, col2 = lin1 + rel_lin, col1 + rel_col
        if lin2 < 0 or col2 < 0 or \
           lin2 >= size or col2 >= size:
            return False
        size = int(math.sqrt(len(self.tabuleiro)))
        pos1 = lin1 * size + col1
        pos2 = lin2 * size + col2
        self.tabuleiro[pos1], self.tabuleiro[pos2] = self.tabuleiro[pos2], self.tabuleiro[pos1]
        return True

    def move_cima(self): return self._move(-1, 0)
    def move_baixo(self): return self._move(1, 0)
    def move_esquerda(self): return self._move(0, -1)
    def move_direita(self): return self._move(0, 1)
        
    def __eq__(self, other):
        return self.tabuleiro == other.tabuleiro
    
    def __repr__(self):
        return str(self.tabuleiro)

def busca_profundidade(jogo, tentativas):
    print jogo.tabuleiro
    if jogo.tabuleiro == objetivo:
        #sys.exit()
        return # solucao
    tentativas.append(jogo.tabuleiro)
    jogo2 = jogo.copy()
    if jogo2.move_cima():
        if jogo2.tabuleiro not in tentativas:
            bt(jogo2, tentativas)
    jogo2 = jogo.copy()
    if jogo2.move_baixo():
        if jogo2.tabuleiro not in tentativas:
            bt(jogo2, tentativas)
    jogo2 = jogo.copy()
    if jogo2.move_esquerda():
        if jogo2.tabuleiro not in tentativas:
            bt(jogo2, tentativas)
    jogo2 = jogo.copy()
    if jogo2.move_direita():
        if jogo2.tabuleiro not in tentativas:
            bt(jogo2, tentativas)

def busca_largura(nivel_atual, novo_nivel, tentativas):
    for jogo in nivel_atual:
        print jogo.tabuleiro
        if jogo.tabuleiro == objetivo:
            #sys.exit()
            return # solucao        
        jogo2 = jogo.copy()
        if jogo2.move_cima():
            if jogo2.tabuleiro not in tentativas:
                novo_nivel.append(jogo2)
                tentativas.append(jogo2.tabuleiro)
        jogo2 = jogo.copy()
        if jogo2.move_baixo():
            if jogo2.tabuleiro not in tentativas:
                novo_nivel.append(jogo2)
                tentativas.append(jogo2.tabuleiro)
        jogo2 = jogo.copy()
        if jogo2.move_direita():
            if jogo2.tabuleiro not in tentativas:
                novo_nivel.append(jogo2)
                tentativas.append(jogo2.tabuleiro)
        jogo2 = jogo.copy()
        if jogo2.move_esquerda():
            if jogo2.tabuleiro not in tentativas:
                novo_nivel.append(jogo2)
                tentativas.append(jogo2.tabuleiro)
    busca_largura(novo_nivel, [], tentativas)
    if jogo.tabuleiro == objetivo:
        #sys.exit()
        return # solucao

def busca_gulosa(jogo, tentativas, caminho):
    print jogo.tabuleiro, h(jogo.tabuleiro)
    if jogo.tabuleiro == objetivo:
        print '=== SOLUCAO ==='
        for a in caminho:
            print a
        #sys.exit()
        return # solucao
    tentativas.append(jogo.tabuleiro)
    possibilidades = []
    jogo2 = jogo.copy()
    if jogo2.move_cima():
        if jogo2.tabuleiro not in tentativas:
            possibilidades.append((jogo2, 'C'))
    jogo2 = jogo.copy()
    if jogo2.move_baixo():
        if jogo2.tabuleiro not in tentativas:
            possibilidades.append((jogo2, 'B'))
    jogo2 = jogo.copy()
    if jogo2.move_esquerda():
        if jogo2.tabuleiro not in tentativas:
            possibilidades.append((jogo2, 'E'))
    jogo2 = jogo.copy()
    if jogo2.move_direita():
        if jogo2.tabuleiro not in tentativas:
            possibilidades.append((jogo2, 'D'))
    possibilidades.sort(cmp=lambda x, y : h(x[0].tabuleiro) - h(y[0].tabuleiro))
    for jogo, dir in possibilidades:
        caminho.append(jogo)
        busca_gulosa(jogo, tentativas, caminho)
        caminho.pop()

class Visita:
    """
    Representa uma visita feita durante um encaminhamento.

    Cada visita armazena o caminho percorrido, vizinhos que aquele no ainda
    pode visistar, estimativa ao destino (h(x)) e custo do encaminhamento ate
    atingir aquele no (g(x)).
    """ 
    def __init__(self, jogo, caminho, vizinhos, custo, estimativa):
        self.jogo = jogo
        self.caminho = caminho
        self.vizinhos = vizinhos
        self.estimativa = estimativa
        self.custo = custo
    
    def __cmp__(self, other):
        return (self.estimativa + self.custo) - (other.estimativa + other.custo)
    
    def __repr__(self):
        return repr(self.jogo) + ":" + str(self.estimativa + self.custo)
    
def busca_a_estrela():
    jogo = Jogo()
    novos_vizinhos = []
    jogo2 = jogo.copy()
    if jogo2.move_cima():
        novos_vizinhos.append(jogo2)
    jogo2 = jogo.copy()
    if jogo2.move_baixo():
        novos_vizinhos.append(jogo2)
    jogo2 = jogo.copy()
    if jogo2.move_esquerda():
        novos_vizinhos.append(jogo2)
    jogo2 = jogo.copy()
    if jogo2.move_direita():
        novos_vizinhos.append(jogo2)
    visitas = [Visita(jogo, [jogo], novos_vizinhos, 0, h(jogo.tabuleiro))]
    tentativas = [jogo.tabuleiro]
    while visitas[0].jogo.tabuleiro != objetivo:
        if DEBUG:
            visitas_str = list(visitas)
            visitas_str.sort()
            print visitas_str
        visita_atual = heapq.heappop(visitas)
        for vizinho in visita_atual.vizinhos:
            novos_vizinhos = []
            jogo2 = vizinho.copy()
            if jogo2.move_cima():
                if jogo2.tabuleiro not in tentativas:
                    novos_vizinhos.append(jogo2)
                    tentativas.append(jogo2.tabuleiro)
            jogo2 = vizinho.copy()
            if jogo2.move_baixo():
                if jogo2.tabuleiro not in tentativas:
                    novos_vizinhos.append(jogo2)
                    tentativas.append(jogo2.tabuleiro)
            jogo2 = vizinho.copy()
            if jogo2.move_esquerda():
                if jogo2.tabuleiro not in tentativas:
                    novos_vizinhos.append(jogo2)
                    tentativas.append(jogo2.tabuleiro)
            jogo2 = vizinho.copy()
            if jogo2.move_direita():
                if jogo2.tabuleiro not in tentativas:
                    novos_vizinhos.append(jogo2)
                    tentativas.append(jogo2.tabuleiro)
            novo_caminho = visita_atual.caminho + [vizinho]
            nova_visita = Visita(vizinho, \
                                  novo_caminho, \
                                  novos_vizinhos, \
                                  visita_atual.custo + 1, \
                                  h(vizinho.tabuleiro))
            heapq.heappush(visitas, nova_visita)
            melhor_caminho = visitas[0].caminho
    print '=== SOLUCAO ==='
    for c in melhor_caminho:
        print c

def main():
    jogo = Jogo()
    print 'A*'
    busca_a_estrela()
    print 'GULOSA'
    busca_gulosa(jogo, [], [inicial])
    print 'PROFUNDIDADE'
    busca_profundidade(jogo, [])
    print 'LARGURA'
    busca_largura([jogo], [], [])

if __name__ == '__main__':
    main()
